function private inrange(convver, concave, vers, p0, p1)
{
	var vp, v1, v2;
	if (p0 == 0) {
		v1 = convver[vers-1] - convver[0];
		v2 = convver[1]      - convver[0];
	} else if (p0 == vers-1) {
		v1 = convver[p0-1] - convver[p0];
		v2 = convver[0]    - convver[p0];
	} else {
		v1 = convver[p0-1] - convver[p0];
		v2 = convver[p0+1] - convver[p0];
	}
	vp = convver[p1] - convver[p0];
	if (concave[p0]) {
		if (vz(vp*v1) >= 0 | vz(v2*vp) >= 0) {
			return TRUE;
		}
	} else {
		if (vz(vp*v1) >= 0 & vz(v2*vp) >= 0) {
			return TRUE;
		}
	}
	return FALSE;

}

function private iscross(convver, vers, p0, p1)
{
	var i;
	var site3, site4, sa, sb;
	var v1, v2, v3, v4;
	var center;
//var v3_;
//DrawLine(PolyGetVertex(p0), PolyGetVertex(p1));

	if (p1 == p0 | p1 == p0+1 | p1 == p0-1
	 | (p0 == 0 & p1 == vers-1) | (p1 == 0 & p0 == vers-1)) {
//DrawLine(PolyGetVertex(p0), PolyGetVertex(p1));
		return TRUE;
	}
	v1 = convver[p0];
	v2 = convver[p1];
	v4 = convver[vers-1];
	site4 = vz((v4-v1) * (v2 - v1));
	site3 = site4;
//v3_ = PolyGetVertex(vers-1);
	for (i = 0; i < vers; i++) {
		v3 = v4;
		v4 = convver[i];
//DrawLine(v3_, PolyGetVertex(i));
		if (site4 != 0) {
			site3 = site4;
		}
		site4 = vz((v4-v1) * (v2 - v1));
		sa = vz((v1-v3)*(v4-v3));
		sb = vz((v2-v3)*(v4-v3));
		if ((site3 < 0 & site4 > 0) | (site3 > 0 & site4 < 0)) {
			if ((sa < 0 & sb > 0) | (sa > 0 & sb < 0)) {
//print("outrange site3=", site3, "site4=", site4, "sa=", sa, "sb=", sb, "\n");
//WaitEvent();
//DrawLine(v3_, PolyGetVertex(i));
//DrawLine(PolyGetVertex(p0), PolyGetVertex(p1));
				return TRUE;
			}
		}
//DrawLine(v3_, PolyGetVertex(i));
//v3_ = PolyGetVertex(i);
	}
//print("inrange\n");
//WaitEvent();
//DrawLine(PolyGetVertex(p0), PolyGetVertex(p1));
	return FALSE;
}

function ConvexConvertMain()
{
	var convver[MAXVERTEX];
	var concave[MAXVERTEX];
	var v1, v2;
	var vers, i;
	var nvec, vec0, vec1;
	var convmat;
	var convex = TRUE;
	var minpos, minx, miny, x, y;
	var begin, end;
	var cvec;
	vers = PolyVertexs();
	if (vers < 4) {
		return FALSE;
	}
	PolySetVertex(PolyGetVertex(0),vers);
	PolySetVertex(PolyGetVertex(1),vers+1);
	v1 = unit(Position(PolyGetVertex(0)-PolyGetVertex(vers-1)));
	v2 = unit(Position(PolyGetVertex(1)-PolyGetVertex(0)));
	vec0 = v1 * v2;
	nvec = vec0;
	for (i = 1; i < vers; i++) {
		v1 = v2;
		v2 = unit(Position(PolyGetVertex(i+1)-PolyGetVertex(i)));
		vec1 = v1 * v2;
		if (vec0 . vec1 <= 0.0001) {
			nvec = nvec - vec1;
			convex = FALSE;
		} else {
			nvec = nvec + vec1;
		}
	}
	if (convex | (abs(nvec) < 0.0001)) {
		return FALSE;
	}
	convmat = CalRotMatrix(nvec, vector(0,0,1));

	minpos = -1;
	minx = 0;
	miny = 0;
	ViewCursor( OFF );
	DrawCurrent(TRUE);
	ViewCursor( ON );
	for (i = 0; i < vers; i++) {
		convver[i] = Position(PolyGetVertex(i) * convmat);
		x = vx(convver[i]);
		y = vy(convver[i]);
		if (minpos < 0 | y < miny | (y == miny & x < minx)) {
			minpos = i;
			minx = x;
			miny = y;
		}
	}
	if (minpos == 0) {
		v1 = unit(convver[0]-convver[vers-1]);
		v2 = unit(convver[1]-convver[0]);
	} else if (minpos == vers-1) {
		v1 = unit(convver[minpos]-convver[minpos-1]);
		v2 = unit(convver[0]-convver[minpos]);
	} else {
		v1 = unit(convver[minpos]-convver[minpos-1]);
		v2 = unit(convver[minpos+1]-convver[minpos]);
	}
	if (vz(v1 * v2) < 0) {
//		convmat = rot(convmat, AXISY, 180);
		convmat = scale(convmat, 1,1,-1);
	}
	PolyShiftVertex(minpos);
	do {
		for (i = 0; i < vers; i++) {
			convver[i] = Position(PolyGetVertex(i) * convmat);
		}
		convver[vers] = convver[0];
		convver[vers+1] = convver[1];
		v2 = unit(convver[0]-convver[vers-1]);

		minpos = -1;
		minx = 2;
		for (i = 0; i < vers; i++) {
			v1 = v2;
			v2 = unit(convver[i+1]-convver[i]);
//DrawLine(Vertex(0,0,0), PolyGetVertex(i));
//print("\nconcave=", vz(v1 * v2));
//WaitEvent();
//DrawLine(Vertex(0,0,0), PolyGetVertex(i));
			if (vz(v1 * v2) <= 0.0001) {
				concave[i] = TRUE;
				x = v1 . v2;
				if (x < minx) {
					minpos = i;
					minx = x;
				}
			} else {
				concave[i] = FALSE;
			}
		}
		if (minpos <= 0) {
			break;
		}
		if (minpos == 0) {
			v1 = unit(convver[0]-convver[vers-1]);
			v2 = unit(convver[0]-convver[1]);
		} else if (minpos == vers-1) {
			v1 = unit(convver[minpos]-convver[minpos-1]);
			v2 = unit(convver[minpos]-convver[0]);
		} else {
			v1 = unit(convver[minpos]-convver[minpos-1]);
			v2 = unit(convver[minpos]-convver[minpos+1]);
		}
		begin = minpos;
		if (abs(v1+v2) < 0.0001) {
			cvec = getvector(vec(UNIT_MATRIX, v1, vector(0,0,1)), 1);
		} else {
			cvec = unit(v1 + v2);
		}
		minpos = -1;
		minx = -1;
		for (i = 0; i < vers; i++) {
			if (inrange(convver, concave, vers, begin, i)
			  & inrange(convver, concave, vers, i, begin)) {
				if (!iscross(convver, vers, begin, i)) {
					v1 = unit(convver[i]-convver[begin]);
					x = cvec . v1;
//print("\ncos=", x);
//DrawLine(PolyGetVertex(begin), PolyGetVertex(i));
//WaitEvent();
//DrawLine(PolyGetVertex(begin), PolyGetVertex(i));
					if (x > minx) {
						minpos = i;
						minx = x;
					}
				}
			}
		}
		if (minpos < 0) {
			break;
		}
		if (minpos < begin) {
			end = begin;
			begin = minpos;
		} else {
			end = minpos;
		}
		if (end - begin + 1 > (vers-(end-begin)+1)) {
			PolyShiftVertex(end);
			PolyVertexs(vers-(end-begin)+1);
			ViewCursor( OFF );
			DrawCurrent(FALSE);
			PolyAppend(TRUE);

			PolyVertexs(vers);
			PolyShiftVertex(vers - (end-begin));
			PolyVertexs(end-begin+1);
			DrawCurrent(TRUE);
			ViewCursor( ON );
			PolySave();
			vers = end - begin + 1;
		} else {
			PolyShiftVertex(begin);
			PolyVertexs(end-begin+1);
			ViewCursor( OFF );
			DrawCurrent(FALSE);
			PolyAppend(TRUE);

			PolyVertexs(vers);
			PolyShiftVertex(end-begin);
			PolyVertexs(vers-(end-begin)+1);
			PolySave();
			DrawCurrent(TRUE);
			ViewCursor( ON );
			vers = vers - (end - begin) + 1;
		}
	} while (TRUE);
	ViewCursor( OFF );
	DrawCurrent(FALSE);
	ViewCursor( ON );
	return TRUE;
}

function ConvexConvert()
{
	var osel;
	osel = Select();
	SelectAll(FALSE);
	Update(OVERWRITE);
	Select(osel);
	while (PolyLoad()) {
		ConvexConvertMain();
	}
}

function TriangleConvert()
{
	var	i, polys, vers;

	polys = SelectPolygons();
	PolyLoadInit();
	for (i = 0; i < polys; i++)
	{
		PolyLoad();
		vers = PolyVertexs();
		while( vers > 3 )
		{
			PolyVertexs( 3 );
			PolyAppend( TRUE );
			PolyVertexs( vers );
			PolyDelVertex( 1 );
			vers--;
		}
		PolySave();
	}
}
